/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 22
 * Time: 10:56
 */
//牛客 链表内指定区间反转
//解法一（二次遍历）
class Solution2 {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for(int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }
        ListNode rightNode = pre;
        for(int i = 0; i < n - m + 1; i++) {
            rightNode = rightNode.next;
        }

        ListNode leftNode = pre.next;
        ListNode cur = rightNode.next;//pre、leftNode、rightNode、cur不能再动了，因为后面断开节点后要通过这些引用重新连接节点

        pre.next = null;
        rightNode.next = null;

        ListNode pre1 = null;
        ListNode leftNode1 = leftNode;
        while(leftNode1 != null) {
            ListNode leftNode1Next = leftNode1.next;
            leftNode1.next = pre1;
            pre1 = leftNode1;
            leftNode1 = leftNode1Next;
        }

        pre.next = rightNode;
        leftNode.next = cur;
        return dummyNode.next;
    }
}




//解法二，对解法一进行优化（一次遍历）
class Solution3 {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for(int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }

        ListNode cur = pre.next;
        for(int i = 0; i < n - m; i++) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = pre.next;
            pre.next = curNext;
        }
        return dummyNode.next;
    }
}
